We learned the rules for the basic Paxos algorithm in the previous lesson. In this lesson, we will see those rules in action by running Paxos through three different scenarios. We will also see a situation where Paxos makes no progress. Lastly, we will present a solution to making progress and a complete Paxos protocol simulation involving all three roles: proposers, acceptors, and learners. This will also show the role of learners in knowing the current status of a slot's chosen value.

Previous value already chosen#

Let's see what happens when a value has already been chosen, and a new proposer comes in even with a higher proposal number. According to the rules, the new proposer is obligated to acknowledge the already chosen value and cannot enforce its own value.

Server 5 honors the already chosen value
Server 5 honors the already chosen value

Previous value not chosen, but new proposer sees it#

Due to network delays, messages can reach different servers at different times. The messages of different servers can intermingle. Even specific servers might take different times to process and act on a request due to variable load conditions. In the following example, server 5's proposal sees an older proposal value being accepted at server 3. As per the rules, server 5 acknowledges the value that has been accepted at server 3.

Server 5 sees a value accepted at server 3 and honors it in its accept requests
Server 5 sees a value accepted at server 3 and honors it in its accept requests

Previous value not chosen, new proposer doesn't see it#

It might be possible that the proposer at server 5 contacts a majority but does not yet see a proposal acceptance by server 1. In this case, server 5 will be able to get its own value chosen. It is important to note that later on, server 1's acceptor will need to change from the value mov to the chosen value jmp. This example highlights that an accepted value at an acceptor can change, but once a value is chosen, it should remain unchanged.

Sever 3 will reject delayed accept from server 1 because it has already promised for a higher valued proposal number for server 5
Sever 3 will reject delayed accept from server 1 because it has already promised for a higher valued proposal number for server 5

Liveness issues in the Paxos algorithm#

We will now discuss Paxos's liveness challenges in this section. We will also see the role of the learners in a full-fledged example where three participants are involved.

The dueling proposers#

The Paxos protocol says that an acceptor should always promise to a proposal if it has a proposal number higher than the one the acceptor has already promised. This condition can lead to a situation where the accept requests sent by the proposer are always being rejected by the acceptors (that promised to that proposer earlier). This happens because those acceptors receive prepare requests with greater proposal numbers before they receive the accept requests for the proposal they promised. And the acceptors have to promise to such proposals according to the protocol we have seen in the previous lesson.

If every time the acceptors receive a prepare request with a higher proposal number before receiving an accept request against a proposal that the acceptors promised earlier, none of the accept requests will be accepted (for example, server 3 in the following illustration is going through this situation). No progress is being made, and none of the proposers can pass step 2 of the protocol. Therefore, a value can never be chosen in this case. This dueling proposer situation is shown in the following illustration. Servers 1 and 5 are dueling to get their value accepted with no luck.

Two dueling proposers with no progress
Two dueling proposers with no progress

Let's see dueling proposers in action.

Created with Fabric.js 3.6.6
Consider there are three members of the group, A, B, and C, and each member is performing all the roles

1 of 22

Created with Fabric.js 3.6.6
The handshake phase starts, in which the proposers send their proposal IDs

2 of 22

Created with Fabric.js 3.6.6
Each of the proposers needs a proposal ID as an identity of their proposal, and to help indicate the latest proposal

3 of 22

Created with Fabric.js 3.6.6
Proposers request an incremental unique ID generator service to generate proposal number

4 of 22

Created with Fabric.js 3.6.6
Proposer A gets proposal ID 1

5 of 22

Created with Fabric.js 3.6.6
Proposer A sends their proposal ID to the acceptors by sending a prepare request

6 of 22

Created with Fabric.js 3.6.6
Meanwhile proposer B also gets proposal ID which is 2

7 of 22

Created with Fabric.js 3.6.6
Acceptors A and B promise to proposer A at proposal ID 1, and note down the promised proposal ID

8 of 22

Created with Fabric.js 3.6.6
Proposer A receives promises from majority of the acceptors, 2 out of 3 group members in total

9 of 22

Created with Fabric.js 3.6.6
Proposer A can continue with the step 2 of the protocol

10 of 22

Created with Fabric.js 3.6.6
Proposer A has met the conditions that allow it to send an accept request and pick a value of its choice because it didn't receive any accepted value in responses

11 of 22

Created with Fabric.js 3.6.6
Meanwhile, proposer B sends a prepare request for proposal ID 2 to the acceptors

12 of 22

Created with Fabric.js 3.6.6
The acceptors promise to the prepare request for proposal ID 2 because it is greater than proposal ID 1, which the the acceptors already promised to

13 of 22

Created with Fabric.js 3.6.6
Proposer B gets promises from majority and is therefore eligible to send an accept request

14 of 22

Created with Fabric.js 3.6.6
Proposer A enters step 2 of the protocol, which is the value acceptance phase

15 of 22

Created with Fabric.js 3.6.6
Proposer A picks a value of its choice, val_A, and sends an accept request to the acceptors

16 of 22

Created with Fabric.js 3.6.6
The acceptors see that they no longer have the promise at proposal ID 1 because they promised to another proposal with a higher proposal number

17 of 22

Created with Fabric.js 3.6.6
The acceptors send a rejection to the proposer A for proposal ID 1 and val_A, and also send in a response the latest promised proposal ID

18 of 22

Created with Fabric.js 3.6.6
Proposer A requests the incremental unique ID generator to generate another proposal number

19 of 22

Created with Fabric.js 3.6.6
The proposer B gets majority votes and can send accept request, but before it does that, the proposer C sends prepare request to the acceptors

20 of 22

Created with Fabric.js 3.6.6
The acceptors promise to propose C at proposal ID 3 and it is greater than 2 (the last promised proposal) and the latest

21 of 22

Created with Fabric.js 3.6.6
The proposer B is eligible to send an accept request but it will get a rejection because the acceptor no longer has the promise with proposal ID 3

22 of 22

The distinguished proposer as a solution to dueling proposers#

To avoid the dueling proposers' situation, only a single proposer, called the distinguished proposer, is allowed to issue proposals. We can choose one of the proposers as a distinguished proposer so that all clients' requests have to funnel through it. A node with the highest ID can be elected as the current distinguished proposer. Nodes can share messages with each other to claim the leadership of being a distinguished proposer.

A leased-based scheme can be used where the current distinguished proposer reaffirms its position by sending messages to all nodes. If other nodes do not listen to such messages, they can initiate a fresh election algorithm. Even if there are two leaders at some point (for example, when some nodes were not able to hear from the leader due to network delays or partitioning), such a scenario does not pose a safety risk. A distinguished proposer helps make progress and eventually chooses a value. The protocol simulation with the distinguished proposer is shown in the following illustration:

Note: Having a distinguished proposer is an optimization and not a requirement. However, most Paxos implementations are based on the distinguished proposer.

Created with Fabric.js 3.6.6
Consider there are three members of the group, A, B, and C, and each member is performing all the roles

1 of 22

Created with Fabric.js 3.6.6
To avoid a dueling proposer situation, one proposer is selected to propose at a single time, and it is called the distinguished proposer

2 of 22

Created with Fabric.js 3.6.6
The distinguished proposer is selected based on the highest node/member ID

3 of 22

Created with Fabric.js 3.6.6
Let's assume that A is selected as the distinguished proposer

4 of 22

Created with Fabric.js 3.6.6
Proposer A requests the incremental unique ID generator to generate a proposal number

5 of 22

Created with Fabric.js 3.6.6
Proposer A requests the incremental unique ID generator to generate a proposal number

6 of 22

Created with Fabric.js 3.6.6
Proposer A gets proposal number 1

7 of 22

Created with Fabric.js 3.6.6
Proposer A's proposal identity is 1

8 of 22

Created with Fabric.js 3.6.6
Proposer A needs promises from majority acceptors on proposal ID 1, for which it needs to send prepare requests to the acceptors

9 of 22

Created with Fabric.js 3.6.6
Proposer A sends a prepare request to all acceptors

10 of 22

Created with Fabric.js 3.6.6
Proposer A promises with itself

11 of 22

Created with Fabric.js 3.6.6
Proposer A gets a promise from B. It has two promises, including its own promise.

12 of 22

Created with Fabric.js 3.6.6
Proposer A receives promises from the majority. It has 2 promises from a total of 3 group members and is eligible to enter phase 2 of the protocol.

13 of 22

Created with Fabric.js 3.6.6
Proposer A is ready to enter step 2 of the protocol

14 of 22

Created with Fabric.js 3.6.6
Since proposer A gets promises from majority acceptors, it sends accept requests to those acceptors with a value of its own choice because it received no values in response to prepare requests

15 of 22

Created with Fabric.js 3.6.6
Proposer A receives acceptance from majority on val_A

16 of 22

Created with Fabric.js 3.6.6
val_A is chosen because majority acceptors accepted this value

17 of 22

Created with Fabric.js 3.6.6
Acceptors also broadcast accepted requests to other members of the majority set of learners, so that in case A fails, we don't lose the results

18 of 22

Created with Fabric.js 3.6.6
Learner B receives accepted messages from majority on proposal number 1 and val_A, so it considers val_A as a final chosen value

19 of 22

Created with Fabric.js 3.6.6
Learner B broadcasts the final chosen value to Learner C

20 of 22

Created with Fabric.js 3.6.6
Learner B broadcasts the final chosen value to Learner C

21 of 22

Created with Fabric.js 3.6.6
All the members of the group know about the final chosen value

22 of 22

The distinguished proposer is the only one who will try issuing proposals until it makes a value chosen. If the distinguished proposer fails before it reaches a consensus on a single value, then we need to elect another distinguished proposer.

Points to ponder

Question 3

Isn’t funneling each client request via a single distinguished proposer a scalability issue?

Hide Answer

Usually, a single proposer is not a scalability issue because there are no dueling proposers (the network is less busy and nodes are less busy processing dueling messages) and each request gets chosen quickly.

We might need other techniques, such as state sharding, where each shard is managed by a different Paxos state machine to deal with any scalability issues.

3 of 3

We now know the workflow of the Paxos protocol. In the next lesson, we will revisit many of Paxos's rules to understand their rationale. While it may appear repetitive, this approach is intentional and aims to dispel the notion among practitioners that Paxos is challenging to grasp. By examining many examples, the core rules should become clearer. If you are short on time, you may skip the next lesson.

Basic Paxos Protocol Design

The Rationale behind Paxos Design Choices